1. Field of the Invention
This invention relates to a parallel adder circuit for adding signed binary numbers in parallel, and more particularly to a parallel adder circuit for use in multipliers.
2. Description of the Related Art
The multiplication of a binary number by a binary number is effected by first attaining partial products of the multiplicand and respective bits of the multiplier and then adding all the partial products thus obtained together. In the normal multiplication, the partial products equal in number to the bits of the multiplier are obtained, thus increasing the number of times for adding the partial products to lower the operation speed. Therefore, in the high speed multiplier, the Booth's algorithm as described below is used to decrease the number of partial products.
Assume that in the case of using the second order Booth's algorithm, multiplicand is set to EQU A (=-2.sup.n-1 .multidot.a.sub.n-1 +2.sup.n-2 .multidot.a.sub.n-2 + . . . +2a.sub.1 +a.sub.0)
and the multiplier is set to EQU B (=-2.sup.n-1 .multidot.b.sub.n-1 +2.sup.n-2 .multidot.b.sub.n-2 + . . . +2b.sub.1 +b.sub.0).
In this case, if n is an even number, then the product D of A and B can be obtained as follows: ##EQU1## where ppi is a partial product and ppi=A(b.sub.2i-1 +b.sub.2i -2b.sub.2i+1).
The multiplication utilizing the Booth's algorithm has two features. One of the features is that the number of partial products to be added is reduced to one-half that of partial products in the case of the ordinary multiplication algorithm. The other feature is that partial product ppi is represented in terms of 2's complement, and the operation with a sign can be effected without particular correction.
FIG. 1 shows the process of a multiplication of 8 bits.times.8 bits using the Booth's algorithm. In this case, most significant bits a7 and b7 of multiplicand A and multiplier B and most significant bit d14 of the product D are sign bits. Four partial products pp0 to pp3 are obtained as partial product ppi. Further, in FIG. 1, numerals in the frame surrounded by broken lines 10 are extended sign bits.
With the Booth's algorithm, the operation accompanied by a sign can be effected without particular correction, but it is necessary to extend sign bits of the partial products as shown in FIG. 1. In a circuit such as carry save adder (CSA) which sequentially performs additions, the sign bits may be extended by two bits at one time. However, in an adding circuit such as the Wallace tree, since a large number of bits at the same digits of the partial products are simultaneously added together, it becomes necessary to extend more sign bits than in the case of CSA.
FIG. 2 is a circuit diagram showing part of the construction of the prior art multiplier for multiplication of 12 bits.times.12 bits using the Booth's algorithm. One-bit partial products p.sub.i,j (i, j=0, 1, 2, - - - , 12) are selectively supplied to full adders (FA) 11. Sum outputs S and carry outputs C from full adders 11 are respectively supplied to half adders (HA) 12 and full adders 11. Sum outputs S and carry outputs C from latter full adders 11 are supplied to two-input high speed adder (HSA) 13 which is used to obtain products d0 to d22. In practice, Booth's decoder and selector are used to obtain one-bit partial products p.sub.i,j, but they are not shown for brevity. Full-adders 11 and half adders 12 are connected to form the Wallace tree.
In the multiplier, six partial products pp0 to pp5 are added together by the Wallace tree to make two binary numbers which are then added together by two-input high speed adder 13 to provide products d0 to d22. Assume now that the number of partial products ppi to be added is six. Then, the number of addition stages which is called the depth of Wallace tree is 3. However, if partial product ppi is negative, it becomes necessary to add "1" to the least significant bit (LSB) of the output from the selector in order to represent the partial product in terms of 2's complement. Therefore, in the multiplier, the depth of Wallace tree is 4.
In the multiplier, the sign bits of the partial products are extended to the most significant bit (MSB) or 22nd bit and supplied to the Wallace tree. Therefore, those ones of full adders 11 which are hatched in FIG. 2 are connected to receive extended sign bits p12.0, p12.1 and p12.2. Thus, the full adders which receive only the sign bits are redundant, additionally necessitating a corresponding number of full adders and making the multiplier complicated in construction.
Further, a multiplier shown in FIG. 3 is known in the prior art. In the multiplier, the redundant full adders in the multiplier of FIG. 2 are omitted and a single full adder 14 connected to receive extended sign bits is provided. Thus, sum output S and carry output C of fully adder 14 can be extended towards upper bits.
In the multiplier, the fan out of fully adder 14 hatched in FIG. 3 and used to add sign bits p12.0, p12.1 and p12.2 is large. Therefore, the signal propagation delay time becomes large, making time for multiplication long. Further, since it is necessary to extend both the sum output and carry output, it is impossible to omit adders other than the redundant full adders shown in FIG. 2, making the circuit construction complicated.